package code.oldCode.comBineAndPermute;

import java.util.*;

/**
 * @author cuihaoran
 * @date 2024/9/23
 */
public class CombineAndPermute {
    /**
     * 组合问题
     */
    /**
     * 39 组数总和
     *
     * @param candidates
     * @param target
     * @return
     */
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> lists = new ArrayList<>();
        backTrace(0, 0, candidates, target, lists, new ArrayList<>());
        return lists;
    }

    public void backTrace(int start, int value, int[] candidates, int target, List<List<Integer>> lists, List<Integer> list) {
        if (value == target) {
            lists.add(new ArrayList<>(list));
            return;
        } else if (value > target) {
            return;
        }

        for (int i = start; i < candidates.length; i++) {
            list.add(candidates[i]);
            backTrace(i, value + candidates[i], candidates, target, lists, list);
            list.remove(list.size() - 1);
        }
    }

    /**
     * 40 组数总和Ⅱ
     *
     * @param candidates
     * @param target
     * @return
     */
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        int len = candidates.length;
        List<List<Integer>> lists = new ArrayList<>();
        if (len == 0) {
            return lists;
        }
        Arrays.sort(candidates); // 排序很重要
        Deque<Integer> path = new ArrayDeque<>(len);
        traceBack(candidates, len, 0, target, path, lists);
        return lists;
    }

    public void traceBack(int[] candidates, int len, int begin, int target, Deque<Integer> path, List<List<Integer>> lists) {
        if (target == 0) {
            lists.add(new ArrayList<>(path));
            return;
        } else if (target < 0) {
            return;
        }
        for (int i = begin; i < len; i++) {
            // 如果当前值和上一个值相同，说明可能发生重复，且不可能有新组合，新组合在上一次找完了
            if (i > begin && candidates[i] == candidates[i - 1])
                continue;
            // dfs
            path.addLast(candidates[i]);
            traceBack(candidates, len, i + 1, target - candidates[i], path, lists);
            path.removeLast();
        }
    }

    /**
     * 排列问题
     */
    /**
     * 46 全排列
     *
     * @param nums
     * @return
     */
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> lists = new ArrayList<>();
        int len = nums.length;
        // 用来记录这个位置（数）有没有选过
        boolean[] bools = new boolean[len];
        DFS(nums, lists, bools, len, new ArrayList<>());
        return lists;
    }

    void DFS(int[] nums, List<List<Integer>> lists, boolean[] bools, int len, List<Integer> list) {
        if (list.size() == len) {
            lists.add(new ArrayList<>(list));
            return;
        }

        for (int i = 0; i < len; i++) {
            // 如果没有被选过，则开始DFS
            if (bools[i])
                continue;
            list.add(nums[i]);
            bools[i] = true;
            DFS(nums, lists, bools, len, list);
            bools[i] = false;
            list.remove(list.size() - 1);
        }
    }

    /**
     * 47 全排列Ⅱ
     *
     * @param nums
     * @return
     */
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> lists = new ArrayList<>();
        int len = nums.length;
        boolean[] bools = new boolean[len];
        DFS2(nums, lists, bools, len, new ArrayList<>());

        return lists;
    }

    void DFS2(int[] nums, List<List<Integer>> lists, boolean[] bools, int len, List<Integer> list) {
        if (list.size() == len) {
            lists.add(new ArrayList<>(list));
            return;
        }

        for (int i = 0; i < len; i++) {
            // 原理是：对于在一起的重复的数字，只能从最左面开始，不能中间空一个选下一个，避免重复！
            if (bools[i] || (i > 0 && nums[i] == nums[i - 1] && !bools[i - 1]))
                continue;
            list.add(nums[i]);
            bools[i] = true;
            DFS2(nums, lists, bools, len, list);
            bools[i] = false;
            list.remove(list.size() - 1);
        }
    }

    /**
     * 子集问题
     */
    /**
     * 78 子集
     *
     * @param nums
     * @return
     */
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> lists = new ArrayList<>();
        int len = nums.length;
        searchSet(len, nums, lists, 0, new ArrayDeque<>());

        return lists;
    }

    void searchSet(int len, int[] nums, List<List<Integer>> lists, int start, Deque<Integer> list) {
        lists.add(new ArrayList<>(list));
        if (list.size() == len)
            return;

        for (int i = start; i < len; i++) {
            list.addLast(nums[i]);
            searchSet(len, nums, lists, i + 1, list);
            list.removeLast();
        }
    }

    /**
     * 90 子集Ⅱ
     * @param nums
     * @return
     */
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> lists = new ArrayList<>();
        int len = nums.length;
        Arrays.sort(nums);
        searchSet2(len, nums, lists, 0, new ArrayDeque<>());
        return lists;
    }

    void searchSet2(int len, int[] nums, List<List<Integer>> lists, int start, Deque<Integer> list) {
        lists.add(new ArrayList<>(list));
        if (list.size() == len)
            return;

        for (int i = start; i < len; i++) {
            if (i > start && nums[i] == nums[i - 1])
                continue;
            list.addLast(nums[i]);
            searchSet2(len, nums, lists, i + 1, list);
            list.removeLast();
        }
    }

    public static void main(String[] args) {
        CombineAndPermute combineAndPermute = new CombineAndPermute();
        System.out.println(combineAndPermute.subsetsWithDup(new int[]{1, 2, 2}));
    }
}
